#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void InsertSort(int* a,int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void TestOP()
{
	srand((unsigned int)time(0));
	const int N = 10000;
	int* a = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		a[i] = rand();
	}
	int begin1 = clock();
	InsertSort(a, N);
	int end1 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	free(a);
}
void TestInsertSort()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	PrintArray(a, sizeof(a) / sizeof(int));

	InsertSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
	TestInsertSort();
	
	TestOP();

	return 0;
}